语言模型在信息检索中的平滑方法
引言
在信息检索中文本相关性计算是至关重要的一个特征，关于文本相关性计算时用的比较多的有:词频/频率、tf/idf/tf*idf、bm25、布尔模型、空间向量模型以及语言模型，本文主要是对于[1]的一些学习理解，虽然[1]历史久远，但是可行性高，同时目前也有不少搜索引擎在使用[1]的方法，主要介绍的是语言模型在信息检索中使用的平滑方法，主要侧重点就是性能。
Language Model
现假设query是基于文档d进行生成的,那么给定一个query$q=q_1q_2..q_n$以及一个文档$d=d_1d_2…d_n$,我们比较关心的是$p(d|q)$这个条件概率，即在观察到$q$的情况下生成$d$的一个概率，假设文档中的词是相关独立的，根据贝叶斯公式，则有:
$$p(d|q) \propto p(q|d)p(d)$$
由于在给定$q$下，不同文档的$p(q)$是一样的，这里关注的是排序，所以可以直接将$p(q)$进行移除，另外式子右侧的$p(d)$为文档$d$对于任何$q$的相关性先验，在$p(q|d)$就是在给定$d$下生成$q$的概率，也就是文档$d$到$q$的匹配程度.
为了简单起见，我们假设$p(d)$是均匀分布的，这样的话$p(d)$就不会影响排序，那么信息检索的问题就会转为一个一元语言模型:
$$p(q|d) = \prod_i p(q_i|d)$$
大多数平滑的方法都会使用两类分布:
- 一类是对于在文档中出现的词的模型$p_s(w|d)$
- 另一个是没有出现在文档中的词的模型$p_u(w|d)$
这样的话在一个$q$中根据词在文档中的出现与否可以写为:
$$\begin{equation}\begin{split}log p(q|d)&= \sum_i log p(q_i|d) \\
&= \sum_{i:c(q_i;d)>0} log p_s(q_i|d) + \sum_{i:c(q_i|d)=0} log p_u(q_i|d) \\
&= \sum_{i:c(q_i;d)>0} log p_s(q_i|d) - \sum_{i:c(q_i;d)>0} log p_u(q_i|d) + \sum_{i:c(q_i;d)>0} log p_u(q_i|d) + \sum_{i:c(q_i|d)=0} log p_u(q_i|d) \\
&= \sum_{i:c(q_i|d)>0} log \frac{p_s(q_i|d)}{p_u(q_i|d)} + \sum_i log p_u(q_i|d) \\
\end{split}\end{equation}$$
其中未在文档中出现的词的概率典型的表示方法就是该词在所有集合中出现的频率:
$$p_u(q_i|d) = \alpha_d p(q_i|C)$$
其中$\alpha_d$为独立于文档的一个常量，$p(q_i|C)$为集合中的语言模型，这样我们就会有
$$log p(q|d) = \sum_{i:c(q_i:d)>0} log \frac{p_s(q_i|d)}{\alpha_d p(q_i|C)} + n log \alpha_d + \sum_i log p(q_i|C)$$
其中$n$为$q$的长度，上面式子的右侧与$d$并没有关系，所以直接去掉也不会影响排序
这样的话检索函数就变成了两部分，第一部分为$q$与$d$相匹配term的权重，第二部分为与$q$无关的一个常量，一般是用于对非匹配term的平滑。
这时候再看下第一部分，其实可以上面$p(q_i|C)$大致可以看为IDF,而$p_s(q_i|d)$又非常向tf,因为上面的Language Model与tf*idf路线还是挺像的。
Smoothing Methods
看了上面的描述，接下来主要讲一下对于$p(w|d)$的估计，最简单的使用数数的方式，最大似然法进行估计为:
$$p_{ml}(w|d) = \frac{w;d}{\sum_w c(w;d)}$$
其实就是词在文档中出现的频率
这种方式对于没出现在文档中的词将会低估（其实就是没值了），因为对于没有在文档中出现的词会给予一个非0概率的平滑。
通常我们会对出现在文档中的词的概率进行一个折损，同时对于未出现在文档中的词的概率给予一个额外的值:
$$ p(w|d)=\left\{
\begin{aligned}
p_s(w|d) & \quad if \quad word \quad w \quad is \quad seen \\
\alpha_d p(w|C) & \quad otherwise\\
\end{aligned}
\right.$$
同时$\alpha_d$将会依赖$d$，如果$p(w|d)$给定的情况下，我们将会有:
$$\alpha_d = \frac{1-\sum_{w:c(w:d)>0} p_s(w|d)}{1-\sum_{w:c(w:d)>0}p(w|C)}$$
因此这里最大的问题是需要计算$p_s(w|d)$,因为在信息检索中对于性能的要求将其高，因此为考虑性能和效果，下面主要简单的介绍三种平滑方式
Jelinek-Mercer
这种方式是融合了最大似然发以及一个置信因子来控制各个模型
$$p_{\lambda} = (1-\lambda)p_{ml}(w|d) + \lambda p(w|C)$$
这种方式非常的高效
Dirichlet
他其实是贝叶斯平滑，然后使用了Dirichlet先验，使用这种可以得到
$$p_{\mu}(w|d) = \frac{c(w;d) + \mu p(w|C)}{\sum_w c(w;d)+ \mu}$$
Absolute discount
这种方式主要是通过降低可见词的概率来完成的,类似Jelinek-Mercer方法,与$1-\lambda$不同的是 使用减去一个常量来完成:
$$p_{\delta } = \frac{max(c(w:d)-\delta,0)}{\sum_w c(w:d)} + \sigma p(w|C)$$
其中$\delta \in [0,1]$,为一个折损常量，$\sigma = \delta|d|_u/|d|$,所以所有的概率之和为1，$|d|_u$为文档中不同
term的数量,$|d|$为文档中term的总数量
另外注意$max(c(w:d)-\delta,0)$中的$c(w:d)$应该是归一化0~1了，这样才可以和$\delta$相减
对于这三种平滑方式的一个表格表示（非常清晰）:
| 平滑方法 | $p_s(w | d)$ | $\alpha_d$ | 参数 |
|---|---|---|---|
Jelinek-Mercer |
$(1-\lambda)p_{ml}(w | d) + \lambda p(w | C)$ | $\lambda$ | $\lambda$ |
Dirichlet |
$\frac{c(w;d) + \mu p(w | C)}{\sum_w c(w;d)+ \mu}$ | $\frac{\mu}{\sum_w c(w;d)+\mu}$ | $\mu$ |
Absolute discount |
$\frac{max(c(w:d)-\delta,0)}{\sum_w c(w:d)} + \frac{\delta | d | _{u}}{ | d |} p(w | C)$ | $\frac{\delta | d | _{u}}{ | d |} $ | $\delta$ |
看上面三种平滑的计算方式都是非常的简单，并且$\alpha$都是可以离线计算，其最终的复杂度为$O(k|q|)$,$k为文档的平均长度$
其实复杂度不用这么多，如果在线查找term时使用二分的话 复杂度仅为$O(log(k)|q|)$
总结
这三种方法比较经典，并且可实现性强，$p_s(w|d)$和$\alpha_d$全部都可以离线计算完成，在线只需要进行简单的求和即可,值得一试~
参考
- Zhai, Chengxiang, and John Lafferty. “A study of smoothing methods for language models applied to ad hoc information retrieval.” Proceedings of the 24th annual international ACM SIGIR conference on Research and development in information retrieval. ACM, 2001.
本作品采用[知识共享署名-非商业性使用-相同方式共享 2.5]中国大陆许可协议进行许可，我的博客欢迎复制共享，但在同时，希望保留我的署名权kubiCode，并且，不得用于商业用途。如您有任何疑问或者授权方面的协商，请给我留言。
